\section{Unit 6：机器学习与优化应用}

\begin{frame}{优化算法中的线性代数结构}
    \begin{block}{优化问题的一般形式}
        \begin{itemize}
            \item 无约束优化：$\min f(\mathbf{x})$
            \item 约束优化：$\min f(\mathbf{x})$ s.t. $g(\mathbf{x}) = 0, h(\mathbf{x}) \leq 0$
            \item 线性代数在梯度、Hessian计算中关键
        \end{itemize}
    \end{block}
    
    \begin{block}{一阶优化方法}
        \begin{itemize}
            \item 梯度下降：$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k)$
            \item 共轭梯度法：利用Krylov子空间
            \item 随机梯度下降：大规模机器学习
            \item 需要矩阵向量乘法运算
        \end{itemize}
    \end{block}
    
    \begin{block}{二阶优化方法}
        \begin{itemize}
            \item 牛顿法：$\mathbf{x}_{k+1} = \mathbf{x}_k - [\nabla^2 f(\mathbf{x}_k)]^{-1} \nabla f(\mathbf{x}_k)$
            \item 拟牛顿法：近似Hessian（BFGS, L-BFGS）
            \item 需要求解线性系统
            \item 矩阵分解技术关键
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{牛顿法与Hessian矩阵}
    \begin{block}{牛顿法原理}
        \begin{itemize}
            \item 二阶泰勒展开：$f(\mathbf{x} + \Delta\mathbf{x}) \approx f(\mathbf{x}) + \nabla f^T\Delta\mathbf{x} + \frac{1}{2}\Delta\mathbf{x}^T H\Delta\mathbf{x}$
            \item 最优步长：$\Delta\mathbf{x} = -H^{-1}\nabla f$
            \item 二次收敛速度（靠近最优解）
        \end{itemize}
    \end{block}
    
    \begin{block}{Hessian矩阵计算}
        \[ H_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j} \]
        \begin{itemize}
            \item 对称矩阵（Clairaut定理）
            \item 凸函数时正定
            \item 计算复杂度：$O(n^2)$存储，$O(n^3)$求逆
            \item 实际使用自动微分或有限差分
        \end{itemize}
    \end{block}
    
    \begin{block}{牛顿法挑战}
        \begin{itemize}
            \item Hessian可能奇异或病态
            \item 需要正则化：$H + \mu I$
            \item 大规模问题计算昂贵
            \item 拟牛顿法更实用
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{梯度近似技术}
    \begin{block}{有限差分法}
        \begin{itemize}
            \item 前向差分：$\frac{\partial f}{\partial x_i} \approx \frac{f(\mathbf{x} + h\mathbf{e}_i) - f(\mathbf{x})}{h}$
            \item 中心差分：更高精度但计算加倍
            \item 步长选择关键：太大截断误差，太小舍入误差
        \end{itemize}
    \end{block}
    
    \begin{block}{自动微分（AD）}
        \begin{itemize}
            \item 前向模式：计算标量函数沿一个方向的导数
            \item 反向模式：计算所有偏导数（反向传播）
            \item 计算复杂度：前向模式$O(n)$，反向模式$O(1)$（相对于输入）
            \item 深度学习中的核心算法
        \end{itemize}
    \end{block}
    
    \begin{block}{随机梯度估计}
        \begin{itemize}
            \item 随机扰动：$\hat{\nabla} f = \frac{f(\mathbf{x} + \epsilon\mathbf{u}) - f(\mathbf{x})}{\epsilon} \mathbf{u}$
            \item 适用于黑盒优化
            \item 方差较大，需要多次采样
            \item 在强化学习中应用
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{Logistic Regression线性求解器}
    \begin{block}{Logistic Regression模型}
        \[ P(y=1|\mathbf{x}) = \sigma(\mathbf{w}^T\mathbf{x}) = \frac{1}{1 + e^{-\mathbf{w}^T\mathbf{x}}} \]
        \[ L(\mathbf{w}) = -\sum_{i=1}^m [y_i\log(\hat{y}_i) + (1-y_i)\log(1-\hat{y}_i)] \]
    \end{block}
    
    \begin{block}{梯度计算}
        \[ \nabla L(\mathbf{w}) = X^T(\hat{\mathbf{y}} - \mathbf{y}) \]
        \[ H(\mathbf{w}) = X^T\text{diag}(\hat{\mathbf{y}} \circ (1-\hat{\mathbf{y}}))X \]
        \begin{itemize}
            \item Hessian半正定，问题凸
            \item 可使用牛顿法求解
        \end{itemize}
    \end{block}
    
    \begin{block}{迭代重加权最小二乘（IRLS）}
        \begin{enumerate}
            \item 线性化：$z = X\mathbf{w} + S^{-1}(\mathbf{y} - \hat{\mathbf{y}})$
            \item 加权最小二乘：$\min \|S^{1/2}(z - X\mathbf{w})\|^2$
            \item 迭代直到收敛
            \item 等价于牛顿法
        \end{enumerate}
    \end{block}
\end{frame}

\begin{frame}{大规模数据中的随机算法}
    \begin{block}{随机化SVD}
        \begin{itemize}
            \item 目标：近似计算大规模矩阵的SVD
            \item 基本思想：通过随机投影降维
            \item 复杂度：$O(mn\log k + (m+n)k^2)$ vs 传统$O(mn\min(m,n))$
        \end{itemize}
    \end{block}
    
    \begin{block}{随机化SVD算法}
        \begin{enumerate}
            \item 生成随机高斯矩阵$\Omega \in \mathbb{R}^{n \times (k+p)}$
            \item 计算$Y = A\Omega$
            \item QR分解：$Y = QR$
            \item 计算$B = Q^TA$
            \item 计算$B$的SVD：$B = \tilde{U}\Sigma V^T$
            \item $U = Q\tilde{U}$
        \end{enumerate}
    \end{block}
    
    \begin{block}{随机化QR分解}
        \begin{itemize}
            \item 类似思想应用于QR分解
            \item 适用于低秩矩阵近似
            \item 在推荐系统、图像处理中应用
            \item 理论保证：Johnson-Lindenstrauss引理
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{随机算法理论保证}
    \begin{block}{Johnson-Lindenstrauss引理}
        对于任意$\epsilon > 0$和整数$m$，存在$k = O(\epsilon^{-2}\log m)$维线性映射$f: \mathbb{R}^n \to \mathbb{R}^k$，使得所有点对距离保持：
        \[ (1-\epsilon)\|u-v\|^2 \leq \|f(u)-f(v)\|^2 \leq (1+\epsilon)\|u-v\|^2 \]
    \end{block}
    
    \begin{block}{矩阵Chernoff界}
        随机投影矩阵的奇异值集中性：
        \[ P(\sigma_{\max}(A\Omega) > (1+\delta)\sigma_{\max}(A)) \leq \text{小概率} \]
    \end{block}
    
    \begin{block}{实际考虑}
        \begin{itemize}
            \item 过采样参数$p$：通常$p=5$或$10$
            \item 幂迭代：改善低奇异值估计
            \item 自适应秩确定
            \item 数值稳定性分析
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{机器学习中的矩阵计算应用}
    \begin{block}{主成分分析（PCA）}
        \begin{itemize}
            \item 数据降维：$X \approx U_k\Sigma_k V_k^T$
            \item 特征脸：人脸识别应用
            \item 大规模PCA：随机化SVD
            \item 增量PCA：流数据
        \end{itemize}
    \end{block}
    
    \begin{block}{推荐系统}
        \begin{itemize}
            \item 矩阵补全：$\min \|P_\Omega(M - UV^T)\|_F^2$
            \item 交替最小二乘（ALS）
            \item 随机梯度下降
            \item 协同过滤
        \end{itemize}
    \end{block}
    
    \begin{block}{深度学习}
        \begin{itemize}
            \item 反向传播：矩阵链式法则
            \item 卷积神经网络：Toeplitz矩阵
            \item 注意力机制：softmax矩阵
            \item 优化器：Adam, RMSprop
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{优化软件与库}
    \begin{block}{数值优化库}
        \begin{itemize}
            \item \textbf{Optim.jl}：Julia优化包
            \item \textbf{SciPy.optimize}：Python科学计算
            \item \textbf{IPOPT}：大规模非线性优化
            \item \textbf{CVXPY}：凸优化建模
        \end{itemize}
    \end{block}
    
    \begin{block}{机器学习框架}
        \begin{itemize}
            \item \textbf{TensorFlow}：Google深度学习框架
            \item \textbf{PyTorch}：Facebook动态图框架
            \item \textbf{JAX}：Google自动微分库
            \item \textbf{Scikit-learn}：Python机器学习
        \end{itemize}
    \end{block}
    
    \begin{block}{线性代数库集成}
        \begin{itemize}
            \item BLAS/LAPACK基础运算
            \item SuiteSparse稀疏求解
            \item CUDA GPU加速
            \item MPI分布式计算
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{本章重点总结}
    \begin{block}{核心内容}
        \begin{itemize}
            \item 优化算法的线性代数结构
            \item 牛顿法与Hessian计算
            \item 梯度近似技术
            \item 大规模随机算法
        \end{itemize}
    \end{block}
    
    \begin{block}{技术要点}
        \begin{itemize}
            \item 自动微分实现高效梯度计算
            \item 随机算法处理大规模数据
            \item 矩阵分解在优化中的应用
            \item 数值稳定性考虑
        \end{itemize}
    \end{block}
    
    \begin{block}{学习目标}
        \begin{itemize}
            \item 理解优化中的矩阵计算
            \item 掌握随机算法原理
            \item 能够实现基本优化算法
            \item 了解实际应用场景
        \end{itemize}
    \end{block}
\end{frame}